<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
            和封闭岛屿，飞地一样，边界首先要处理，但是后面要复原，所以先dfs让其变为A，然后再找中间区域的O变成X，最后把所有A变成O
            
            */
            var solve = function (board) {
                let m = board.length
                let n = board[0].length

                //边界处理
                for (let i = 0; i < m; i++) {
                    for (let j = 0; j < n; j++) {
                        if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                            if (board[i][j] == "O") {
                                dfs(i, j, true)
                            }
                        }
                    }
                }
                for (let i = 0; i < m; i++) {
                    for (let j = 0; j < n; j++) {
                        if (board[i][j] == "O") {
                            dfs(i, j, false)
                        }
                    }
                }

                function dfs(i, j, flag) {
                    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == "X" || board[i][j] == "A") {
                        return
                    }
                    if (flag) {
                        board[i][j] = "A"
                    } else {
                        board[i][j] = "X"
                    }
                    dfs(i - 1, j, flag)
                    dfs(i + 1, j, flag)
                    dfs(i, j - 1, flag)
                    dfs(i, j + 1, flag)
                }

                for (let i = 0; i < m; i++) {
                    for (let j = 0; j < n; j++) {
                        if (board[i][j] == "A") {
                            board[i][j] = "O"
                        }
                    }
                }
                return board
            }
            console.log(
                solve([
                    ["X", "X", "X", "X"],
                    ["X", "O", "O", "X"],
                    ["X", "X", "O", "X"],
                    ["X", "O", "X", "X"],
                ])
            )
        </script>
    </body>
</html>
